package com.lw.leetcode.other.c;

/**
 * other
 * c
 * 793. 阶乘函数后 K 个零
 *
 * @Author liw
 * @Date 2021/5/22 13:13
 * @Version 1.0
 */
public class PreimageSizeFZF {
    public static void main(String[] args) {
        PreimageSizeFZF test = new PreimageSizeFZF();

        // 0
//        int k = 122356844;

        // 5
        int k = 122356843;

        int i = test.preimageSizeFZF(k);
        System.out.println(i);
    }

    public int preimageSizeFZF(int k) {
        long st = 2L;
        long end = Integer.MAX_VALUE * 20L;
        while (st <= end) {
            long m = st + ((end - st) >> 1);
            long index = find(m);
            if (index == k) {
                return 5;
            }
            if (index < k) {
                st = m + 1;
            } else {
                end = m - 1;
            }
        }
        return 0;
    }

    private long find(long n) {
        long sum = 0L;
        while (n != 0L) {
            n = n / 5L;
            sum += n;
        }
        return sum;
    }

}
